ABSTRACT

Contribution:

• an efficient mixed-protocol framework

• extend to multi-input multiplications gates

• construct eff. protocols for several primitives scalar product, matrix multiplication, comparison, maxpool, and equality testing.

1 Introduction

Categories:

• low-latency: using Yao's GC result in constant-round solutions

• high-throughput: using Secret-sharing(SS) conmmunication rounds linear in the multiplicative depth of the citcuit

Mixed-protocol blocks:

• blocks: Arithmetic; Boolean; Yao

• input:
  • A performs ops on fields
  • B and Y perform ops on bits

• approach:
  • A and B using SS-based approach
  • Y using GC-based approach

Practical runtimes: Beaver multiplication triples

在input-independent setup phase 生成一些相关的随机组（Beaver multiplication triple），这些组会在input-dependent online phase使用，加快online的处理速度。

Beaver multiplication triples: [9]D. Beaver. Efficient multiparty protocols using circuit randomization. In CRYPTO, 1991.

1.1 Our Contributions

• an eff. mixed-protocol framework for secure 2PC over an l-bit ring

• secure against a semi-honest adv.

• use an input-independent setup

• focus on online efficiency

Comparison of ABY2.0 and other 2PC protocols

[41] ABY: [13]SPDZ:

• 2-input multiplication: same complexity as SPDZ but using a different approach.

• N-input multiplication gate: constant cost of 2 ring elements and 1 round of itertations

Mixed Protocol Conversions

reduces the number of online rounds from 2 to 1 use correlated OTs(cOT)

Optimization: cOT

[5]cOT

Building Blocks

1.2 Related Work

Eff. SS-based solutions for the dishonest majority over fields [40] [56] Extended to the ring [35]

[82] extended the multiplication from 2-input to N-input using Beaver triple extension

2 Preliminaries

3 2PC in Arithmetic, Boolean and Yao's World

3.1 2PC in Arithmetic World

highlight: its effectiveness towards efficient realisations for multiple input multiplication gates and dot product operations.

3.1.2 Sharing Semantics

Sharing Notions:

• <·>-sharing: $\left(\left[\delta_{v}\right]_{i}, \Delta_{v}\right)$
  • $\delta_v$ is [·]-shared among P0, P1
  • $\Delta_{v}=v+\delta_{v}$
  • $\Delta_v$ is known to both P0, P1 in clean

3.1.3 Protocols

Sharing Protocol

enable party $P_i$ to generate a <·>-sharing of its input value v

$P_i$ generate a <·>-sharing of its input value v

1. (setup)generate a [·]-shared: $[\delta_v]$
   1. $P_i$ samples random $[\delta_v]_i$
   2. two parties together sample $[\delta_v]_{1-i}$

   $P_i$ knows $\delta_{v}=\left[\delta_{v}\right]_{0}+\left[\delta_{v}\right]_{1}$

2. (online) $\Delta_v$ is konwn to both
   1. $P_i$ computes $\Delta_{v}=v+\delta_{v}$
   2. $P_i$ sends it to $P_{1-i}$

REC

• mutually exchange [·] share of $\delta_v$

Linear Operations

Given <a>, <b> and public constants $c_1,c_2$.

Parties can locally compute $\langle\mathbf{y}\rangle=c_{1} \cdot\langle\mathrm{a}\rangle+c_{2} \cdot\langle\mathrm{b}\rangle$

• Pi locally sets $\Delta_{\mathrm{y}}=c_{1} \cdot \Delta_{\mathrm{a}}+c_{2} \cdot \Delta_{\mathrm{b}}$ $\Delta_a,\Delta_b$ is known constants

• then $\left[\delta_{y}\right]_{i}=c_{1} \cdot\left[\delta_{a}\right]_{i}+c_{2} \cdot\left[\delta_{b}\right]_{i}$

Multiplication Protocol

• $\Delta_a,\Delta_b$ are consts.

• They can compute a []-sharing of $\Delta_y$if the parties obtain [·]-sharing of $\delta_{ab}=\delta_a\delta_b$

• The problem of multiplication reduces to generating $[\delta_{ab}]$ given $[\delta_a]$and $[\delta_b]$

Figure 2: Multiplication Protocol

OT based setup MULT

Correlated OTs(cOT) [5]

Execute $\mathrm{cOT}_l^l$ to [·] sharing of $\left[\delta_{\mathrm{a}}\right]_{0}\left[\delta_{\mathrm{b}}\right]_{1}$

• For j : 0 ... $l-1$ ( j-th instance of cOT)
  • P0(sender):
    • inputs correlation function: $f_{j}(x)=x+2^{j}\left[\delta_{a}\right]_{0}$
    • obtains: $\left(m_{j, 0}=r_{j}, m_{j, 1}=\right.r_{j}+2^{j}\left[\delta_{a}\right]_{0})$
  • P1(receiver):
    • inputs choice bit $b_j$ : the $j$-th bit of $[\delta_b]_1$
    • obtains: $m_{j,b_j}$

• [·] share
  • P0: $\left[\left(\left[\delta_{\mathrm{a}}\right]_{0}\left[\delta_{\mathrm{b}}\right]_{1}\right)\right]_{0}=\sum_{j=0}^{\ell-1}\left(-r_{j}\right)$
  • P1: $\left[\left(\left[\delta_{\mathrm{a}}\right]_{0}\left[\delta_{\mathrm{b}}\right]_{1}\right)\right]_{1}=\sum_{j=0}^{\ell-1} m_{j, b_{j}}$

HE-based setupMULT:

1. P0 : use pk0 encrypts its msg $\left[\delta_{\mathrm{a}}\right]_{0},\left[\delta_{\mathrm{b}}\right]_{0}$ P1: use pk0 encrypts $\left[\delta_{\mathrm{a}}\right]_{1},\left[\delta_{\mathrm{b}}\right]_{1}$ and random element $r$

2. P0: sends ciphertext to P1

3. P1: computes ciphertext correspnding to v: $v=\left[\delta_{2}\right]_{0}\left[\delta_{b}\right]_{1}+\left[\delta_{a}\right]_{1}\left[\delta_{b}\right]_{0}-r$ (HE) and sends encryption of v to P0

4. P0: use sk0 decrypt it

• [·] share
  • P0: v
  • P1: r
  • $\left[\delta_{\mathrm{a}}\right]_{0}\left[\delta_{\mathrm{b}}\right]_{1}+\left[\delta_{\mathrm{a}}\right]_{1}\left[\delta_{\mathrm{b}}\right]_{0}=\mathrm{v}+r$

3.1.1 High-level Overview of Our 2PC over Ring

Beaver's technique on gates inputs

Beaver's multiplication triples: [9]

• Setup Phase:
  • interactively generate the multiplication triple: $(\left.\delta_{a}, \delta_{b}, \delta_{a b}\right) \text { with } \delta_{a b}=\delta_{a} \delta_{b}$

• Online Phase:
  • mutually exchange the shares of $\Delta_a,\Delta_b$
  • compute an additive sharing $\Delta_a,\Delta_b$
  • locally compute a sharing of $a\cdot b$

Figure 1: High Level overview of Beaver's and ABY2.0

• requires communicating 4 elements per multiplication(2 elements per reconstruction) REC $\Delta_a,\Delta_b$

Our technique on gate outputs:

• sharing semantics ensure the parties to have the $\Delta$ value the reconstructions of input wires are no longer required

• But inorder to proceed further, a sharing a y needs to be generated. So parties locally compute an additive sharing of $\Delta_y$ and exchange the shares to reconstruct $\Delta_y$

Main Idea:

• shifs the need of reconstruction from per input wire to the output wire.

• For a fan-in 2, it reduces the number of reconstructions from 2 to 1.

3.1.4 Multi-Input Multiplications Gates

3-Input Multiplication gate:

• need to generate the [·]-sharing of $\delta_{a b}, \delta_{b c}, \delta_{a c} \text { and } \delta_{a b c}$

Multi-Input Multiplication gate

• extend to N-input without inflating the online communication.

3.2 2PC in Boolean World

• in a Boolean ring $\Z_{2^1}$

• replace additions with XORS and multiplications with ANDS

• NOT: Negation Protocol

3.3 2PC in Yao World

Main:

Yao World from ABY [41]

For a wire with $v\in0,1$

• P0 (garbler): zero-key on the wire$\langle v\rangle_{0}=\mathrm{K}_{\mathrm{u}}^{0}$

• P1 (evaluator): actual key $\langle v\rangle_{1}=\mathrm{K}_{\mathrm{u}}^{v}$

GC Optimization

free-XOR: [70] Point-and-permute: [11]

4 Mixed Protocol Conversions

4.1 Standard Conversions

Highlight:

• invoke OT in the setup phase only

Y2B

• Goal: generate equivalent Boolean sharing given Yao sharing

• in Yao: LSB of $\mathrm{K}_{\mathrm{u}}^{0} \text { and } \mathrm{K}_{\mathrm{u}}^{\mathrm{u}}$ can reveal u free-XOR property: last bit of zero and one key are distinct

• Y2B:
  1. convert: each party Boolean-shares the LSB of their $\langle\mathrm{u}\rangle_{i}^{\mathbf{Y}}$
  2. obtain u: $\langle\mathbf{u}\rangle^{\mathbf{B}}=\left\langle\mathbf{u}\right\rangle_0^{\mathbf{B}} \oplus\left\langle\mathbf{u}\right\rangle_1^{\mathbf{B}}$
  3. optimization: P0可以在setup phase Boolean-shares $\operatorname{LSB}\left(\mathrm{K}_{\mathrm{u}}^{0}\right)$，因为这是一个随机选的label，而另一个指depends on the value.

Q: 是否泄漏了中间值？

总结来说，就是Y先转换为B中的表示，再根据成立的等式，用B中的运算得到相同的值。 其他也类似。

B2Y

• in Boolean :
  • Pi: locally sets $\mathrm{u}_{i}=(1-i) \cdot \Delta_{\mathrm{u}} \oplus\left[\delta_{\mathrm{u}}\right]_{i}$
  • P0: $u_0=\Delta_u\oplus [\delta_u]_0$
  • P1: $u_1=[\delta_u]_1$
  • satisfy: $u=u_0\oplus u_1$

• B2Y:
  1. convert: each party Yao-shares $u_i$
  2. obtain u: compute $\langle\mathbf{u}\rangle^{\mathbf{Y}}=\left\langle\mathbf{u}_{0}\right\rangle^{\mathbf{Y}} \oplus\left\langle\mathbf{u}_{1}\right\rangle^{\mathbf{Y}}$
  3. optimization: P1可以在setup phase Yao-shares $u_1=[\delta_u]_1$，因为这在setup phase可以确定。

A2Y

• in Arithmetic：
  • Pi: locally sets $\mathrm{v}_{i}=(1-i) \cdot \Delta_{\mathrm{v}}-\left[\delta_{\mathrm{v}}\right]_{i}$
  • satisfy: $\mathrm{v=v_0+v_1}$

• A2Y:
  • convert: each party Yao-shares vi
  • obtain v

Y2A

• setup phase: P0
  • P0 sample a random value r
  • P0 generate $\langle r\rangle^{\mathbf{Y}} \text { and }\langle r\rangle^{\mathbf{A}}$
  • P0 garbles an Adder circuit and sends it to P1 (along with output decoding info)

• online phase:
  • P1 evalute circuit:
    1. input: $\langle\mathbf{v}\rangle^{\mathbf{Y}} \text { and }\langle r\rangle^{\mathbf{Y}}$
    2. output: $\langle\mathrm{v}+r\rangle^{\mathbf{Y}}$
    3. decode: (v+r) in clear
  • obtain:
    1. P1 Arithmetic-shares (v+r)
    2. parties compute $\langle v\rangle^{\mathbf{A}}=\langle v+r\rangle^{\mathbf{A}}-\langle r\rangle^{\mathbf{A}}$

A2B

• similar to A2Y, but it results in a non-constant round protocol (dependent on $l$ )

• constant-round solution: use Y2B(A2Y(·))

Bit2A

• relation in Bit and A:
  • $\mathrm{v}=\mathrm{v}_{0} \oplus \mathrm{v}_{1}$
  • $\mathrm{v^{a}=v_{0}^{a}+v_{1}^{a}-2 v_{0}^{a} v_{1}^{a}}$
  • so: $\mathrm{v^{a}=\left(\Delta_{v} \oplus \delta_{v}\right)^{a}=\Delta_{v}^{a}+\delta_{v}^{a}-2 \Delta_{v}^{a} \delta_{v}^{a} }$

• setup phase: parties interactively generate share: $\mathrm{[\delta_v^a]}$
  • $\mathrm{\delta_{v}=\left[\delta_{v}\right]_{0} \oplus\left[\delta_{v}\right]_{1}}$ $\mathrm{\delta_{v}^{a}=\left[\delta_{v}^{a}\right]_{0}+\left[\delta_{v}^{a}\right]_{1}-2\left(\left[\delta_{v}^{a}\right]_{0}\left[\delta_{v}^{a}\right]_{1}\right)}$
  • execute $\mathrm{cOT}_l^1$ to share $\left[\delta_{v}^{a}\right]_{0}\left[\delta_{v}^{a}\right]_{1}$:
    • P0 (sender): inputs correlation $f_{j}(x)=x+\left[\delta_{v}\right]_{0}^{a}$ and obtain $\left(s_{0}=r, s_{1}=r+\left[\delta_{v}\right]_{0}^{a}\right)$
    • P1 (reciever): inputs the choice bit as $\left[\delta_{v}\right]_{1}$and obtain $s_{[\delta_v]_1}=r+\left[\delta_{v}\right]_{1} \cdot\left[\delta_{v}\right]_{0}^{a}$ $\left[\delta_{v}\right]_{1}=0$: obtain $s_0=r$ $\left[\delta_{v}\right]_{1}=1$: obtain $s_0=r+[\delta_v]_0^a$
  • P0 locally sets $\left[\left(\left[\boldsymbol{\delta}_{v}\right]_{0}^{a}\left[\boldsymbol{\delta}_{v}\right]_{1}^{a}\right)\right]_{0}=-r$
  • P1 locally sets $\left[\left(\left[\boldsymbol{\delta}_{\mathrm{v}}\right]_{0}^{\mathrm{a}}\left[\boldsymbol{\delta}_{\mathrm{v}}\right]_{1}^{\mathrm{a}}\right)\right]_{0}=s_{\left[\delta_{\mathrm{v}}\right]_{1}}$
  • Pi locally sets [·]-share of $[\delta_v^a]_i=(1-i)\cdot[\delta_v]_0^a+i\cdot \left[\delta_{v}\right]_{1}^{a}-2\left[\left(\left[\delta_{v}\right]_{0}^{a}\left[\delta_{v}\right]_{1}^{a}\right)\right]_{i}$

• online phase:
  • convert: Pi locally computes $\left[\mathrm{v}^{\mathrm{a}}\right]_{i}=i \cdot \Delta_{\mathrm{v}}^{\mathrm{a}}+\left(1-2 \Delta_{\mathrm{v}}^{\mathrm{a}}\right) \cdot\left[\delta_{\mathrm{v}}^{\mathrm{a}}\right]_{i}$and Arithmetic-shares $\left[\mathrm{v}^{\mathrm{a}}\right]_{i}$
  • obtain $\mathrm{v^a}$: $\left\langle\mathrm{v}^{\mathrm{a}}\right\rangle^{\mathbf{A}}=\left\langle\left[\mathrm{v}^{\mathrm{a}}\right]_{0}\right\rangle^{\mathbf{A}}+\left\langle\left[\mathrm{v}^{\mathrm{a}}\right]_{1}\right\rangle^{\mathbf{A}}$

B2A

• setup phase: P0
  • P0 sample a random value r
  • P0 generate $\langle r\rangle^{\mathbf{B}} \text { and }\langle r\rangle^{\mathbf{A}}$
  • P0 garbles a boolean circuit and sends it to P1 (along with output decoding info)

• online phase:
  • P1 evalute circuit:
    1. input: $\langle\mathbf{v}\rangle^{\mathbf{B}} \text { and }\langle r\rangle^{\mathbf{B}}$
    2. output: $\langle\mathrm{v}-r\rangle^{\mathbf{B}}$
    3. decode: (v-r) in clear
  • obtain:
    1. P1 Arithmetic-shares (v-r)
    2. parties compute $\langle v\rangle^{\mathbf{A}}=\langle v-r\rangle^{\mathbf{A}}+\langle r\rangle^{\mathbf{A}}$

But it results in a non-constant round protocol in the online phase.

A novel round makes uses of the Bit2A protocol.

• setup phase:
  • fact: $\mathbf{v}=\sum_{j=0}^{\ell-1} 2^{j} \cdot \mathbf{v}[j]$ ( v[j] denotes the jth bit of v)
  • parties possess $\langle v[j]\rangle^{\mathbf{B}} \text { for each } j \in[0, \ell)$: execute l instances of Bit2A conversions

• online phase:
  • for each bit v[j], parties locally compute the [·]-sharing: $[(v[j])^a]$ Bit2A: $\mathrm{v[j]^{a}=\left(\Delta_{v[j]} \oplus \delta_{v[j]}\right)^{a}=\Delta_{v[j]}^{a}+\delta_{v[j]}^{a}-2 \Delta_{v[j]}^{a} \delta_{v[j]}^{a} }$
  • each party locally computes $[\mathrm{v}]_{i}=\sum_{j=0}^{\ell-1} 2^{j} \cdot\left[(\mathrm{v}[j])^{a}\right]_{i}$
  • each party geneate $\left\langle[\mathbf{v}]_{i}\right\rangle^{A}$
  • parties locally computes $\langle\mathbf{v}\rangle^{\mathbf{A}}=\left\langle\left[\mathbf{v}_{0}\right]\right\rangle^{\mathbf{A}}+\left\langle\left[\mathbf{v}_{1}\right]\right\rangle^{\mathbf{A}}$

4.2 Special Conversions

5 Building Blocks for Applications

5.1 Scalar Product

有一种方法是使用n个3.1.3节的乘法，但这样online communication的开销会和vector size n的大小有关，即每次计算出两个向量对应元素的乘积的<·>-share，最后本地加起来。

做出的优化，其实就是先本地求和，再share；

• make the online communication independent of the vector size

5.2 Matrix Multiplication

Notions:

MATMULT:

和乘法类似，唯一需要注意的是计算 $[\mathrm{\gamma_{AB}}]$

5.3 Depth-Optimized Circuits

Parallel-prefix Adders (PPA) [50]

PPA电路可以被优化为提取最高位的电路(BitExt)

5.4 Comparison

• checking x < y = checking the sign of v = x - y

1. parties locally compute $\langle v\rangle=\langle x\rangle-\langle y\rangle$

2. P0, P1 boolean-share a and b respectively.
   1. v = a + b
   2. $a = -\left[\delta_{v}\right]_{0}$
   3. $\mathrm{b}=\Delta_{\mathrm{v}}-\left[\delta_{\mathrm{v}}\right]_{1}$

3. parties use Bit Extraction circuit to compute MSB(v)

5.5 Truncation

在online phase，计算$[\mathrm{y}]=\left[\Delta_{y}\right]-\left[\delta_{y}\right]$。 Each party 截断后再分享，最后再还原。